package tree;

import java.util.ArrayList;
import java.util.List;

public class UniqueBinarySearchTreesii95 {
    public List<TreeNode> generateTrees(int n) {
        return buildTree(1,n);
    }

    private List<TreeNode> buildTree(int begin, int end) {
        List<TreeNode> result = new ArrayList<>();

        if(begin>end){
            result.add(null);
            return result;
        }
        if(begin == end){
            result.add(new TreeNode(begin));
            return result;
        }

        for (int i = begin; i <= end; i++) {
            List<TreeNode> lefts = buildTree(begin,i-1);
            List<TreeNode> rights = buildTree(i+1,end);
            for (int m = 0; m < lefts.size(); m++) {
                for (int mm = 0; mm < rights.size(); mm++) {
                    TreeNode root = new TreeNode(i);
                    root.left = lefts.get(m);
                    root.right = rights.get(mm);
                    result.add(root);
                }
            }
        }

        return result;
    }
}
